package districting;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;

import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.GeometryFactory;
import com.vividsolutions.jts.geom.Point;

public class VoronoiesqueRegion extends Zone {

   private static final double TOLERANCE = 1.0;
   
   private static final int THRESHOLD = 5000;

   private PriorityQueue<Division> divisionsPriQ;

   private List<Point> seedPoints;

   private State state;

   public VoronoiesqueRegion(int numDivisions) {
      this.numDivisions = numDivisions;
      booths = new HashSet<PollingBooth>();
      votingPopulation = 0;
      divisions = new HashMap<DivisionMethod, List<Division>>();
      divisions.put(DivisionMethod.VORONOIESQUE, new ArrayList<Division>());
      pbGeometry = new GeometryFactory().createMultiPoint(new Coordinate[] {});
      divisionsPriQ = new PriorityQueue<Division>(numDivisions,
            new DivisionVotingPopulationComparator());
   }

   public void createFromState(State state) {
      for (PollingBooth pb : state.getBooths()) {
         addPB(pb);
      }

      for (int i = 0; i < numDivisions; i++) {
         Division division = new Division(state.getName() + Integer.toString(i)
               + "_VOR", state.getId() * 100 + i, DivisionMethod.VORONOIESQUE);
         addDivision(division, DivisionMethod.VORONOIESQUE);
         state.addDivision(division, DivisionMethod.VORONOIESQUE);
      }
      this.area = state.getArea();
      this.state = state;
   }

   public void generateSeedPoints(DivisionMethod divMethod) {
      seedPoints = new ArrayList<Point>();
      for (Division division : state.getDivisions(divMethod)) {
         seedPoints.add(division.getPbGeometry().getCentroid());
      }
   }

   public void determineDivisions() {
      HashMap<Division, Point> seedPointsMap = new HashMap<Division, Point>();
      HashMap<Division, PriorityQueue<PollingBooth>> pbListMap = new HashMap<Division, PriorityQueue<PollingBooth>>();

      generateSeedPoints(DivisionMethod.SHORTEST_BISECTING_LINE);
      Iterator<Point> seedPointsIterator = seedPoints.iterator();

      for (Division division : getDivisions(DivisionMethod.VORONOIESQUE)) {
         Point seedPoint = seedPointsIterator.next();
         seedPointsMap.put(division, seedPoint);

         PriorityQueue<PollingBooth> pbList = new PriorityQueue<PollingBooth>(
               booths.size(), new PollingBoothDistanceComparatorB(seedPoints,
                     seedPoint));
         for (PollingBooth pb : state.getBooths()) {
            pbList.add(pb);
         }
         pbListMap.put(division, pbList);
         divisionsPriQ.add(division);
      }

      // Distribute the booths between the divisions
      while (!booths.isEmpty() && !divisionsPriQ.isEmpty()) {
         Division division = divisionsPriQ.remove();
         boolean isContiguous = false;
         PriorityQueue<PollingBooth> pbList = pbListMap.get(division);
         PollingBooth pb = null;
         HashSet<PollingBooth> nonContiguous = new HashSet<PollingBooth>();
         while (!isContiguous && !pbList.isEmpty()) {

            while (!pbList.isEmpty()
                  && (pb = pbList.poll())
                        .getDivision(DivisionMethod.VORONOIESQUE) != null) {
               pb = null;
            }

            if (pb != null) {
               if (division.getBooths().isEmpty()) {
                  isContiguous = true;
               } else {
                  isContiguous = division.getPolygon().intersects(
                        pb.getPolygon());
               }
               if (!isContiguous) {
                  nonContiguous.add(pb);
                  pb = null;
               }
            }
         }
         if (pb != null) {
            // System.out.println("VorReg.dD Polling booth " + pb.getName()
            // + " added to " + division.getName());

            division.addPB(pb);
            booths.remove(pb);
            // System.out.println(division.getPolygon());
            pbList.addAll(nonContiguous);
            divisionsPriQ.add(division);
         } else {
            System.out.println("VorReg.dD - division retired: "
                  + division.getName() + " with voting Population: "
                  + division.getVotingPopulation());
         }
      }
      System.out.println("VorReg.dD.  Unused Booths: " + booths.size());
      for (PollingBooth pb : booths) {
         System.out.println(pb.getName());
      }
   }

   public void determineDivisionsWithStealing() {
      HashMap<Division, Point> seedPointsMap = new HashMap<Division, Point>();
      HashMap<Division, PriorityQueue<PollingBooth>> pbListMap = new HashMap<Division, PriorityQueue<PollingBooth>>();

      generateSeedPoints(DivisionMethod.SHORTEST_BISECTING_LINE);
      Iterator<Point> seedPointsIterator = seedPoints.iterator();

      for (Division division : getDivisions(DivisionMethod.VORONOIESQUE)) {
         Point seedPoint = seedPointsIterator.next();
         seedPointsMap.put(division, seedPoint);

         PriorityQueue<PollingBooth> pbList = new PriorityQueue<PollingBooth>(
               booths.size(), new PollingBoothDistanceComparatorB(seedPoints,
                     seedPoint));
         for (PollingBooth pb : state.getBooths()) {
            pbList.add(pb);
         }
         pbListMap.put(division, pbList);
         divisionsPriQ.add(division);
      }

      // Distribute the booths between the divisions
      boolean noMoreToAdd = false;
      while (!booths.isEmpty() & !noMoreToAdd) {
         HashSet<Division> pausedDivisions = new HashSet<Division>();
         while (!divisionsPriQ.isEmpty()) {

            Division division = divisionsPriQ.remove();
            PriorityQueue<PollingBooth> pbList = pbListMap.get(division);
            PollingBooth pb = null;
            HashSet<PollingBooth> nonContiguous = new HashSet<PollingBooth>();
            HashSet<PollingBooth> nonSatisfactory = new HashSet<PollingBooth>();
            while (!pbList.isEmpty() && pb == null) {
               pb = pbList.poll();

               // Check Contiguity:
               boolean isContiguous = false;
               if (pb != null) {
                  if (division.getBooths().isEmpty()) {
                     isContiguous = true;
                  } else {
                     isContiguous = division.getPolygon().intersects(
                           pb.getPolygon());
                  }
                  if (!isContiguous) {
                     nonContiguous.add(pb);
                     pb = null;
                  }
               }

               // Check Satisfactory:
               boolean isSatisfactory = false;
               if (pb != null) {
                  Division oldDivision = pb
                        .getDivision(DivisionMethod.VORONOIESQUE);
                  if (oldDivision == null) {
                     isSatisfactory = true;
                  } else if (oldDivision.getVotingPopulation() > (division
                        .getVotingPopulation() + THRESHOLD)*TOLERANCE) {
                     // Changing the division which this booth belongs to will
                     // even up the population

                     // Checking whether removing this pb will disconnect the
                     // other region.
                     int numAreas = oldDivision.getPolygon().getNumGeometries();
                     oldDivision.removePB(pb);
                     if (oldDivision.getPolygon().getNumGeometries() > numAreas) {
                        System.out.println("VorReg.dDWS would disconnect");
                        isSatisfactory = false;
                     } else {
                        isSatisfactory = true;
                     }
                     oldDivision.addPB(pb);
                  }
                  if (!isSatisfactory) {
                     nonSatisfactory.add(pb);
                     pb = null;
                  }
               }
            }

            // Add pb if all is good:
            if (pb != null) {
//               System.out.println("VorReg.dD Polling booth " + pb.getName()
//                     + " added to " + division.getName());
               if (pb.getDivision(DivisionMethod.VORONOIESQUE) != null) {
                  Division oldDivision = pb
                        .getDivision(DivisionMethod.VORONOIESQUE);
                  oldDivision.removePB(pb);
                  pbListMap.get(oldDivision).add(pb);
                  System.out.println("VorReg.dD Switching PB: " + pb.getName()
                        + " from " + oldDivision.getName() + " to "
                        + division.getName());
                  divisionsPriQ.remove(oldDivision);
                  divisionsPriQ.add(oldDivision);
               }

               division.addPB(pb);
               booths.remove(pb);
               // System.out.println(division.getPolygon());
               pbList.addAll(nonContiguous);
               pbList.addAll(nonSatisfactory);
               divisionsPriQ.add(division);


               if (!pausedDivisions.isEmpty()) {
                  if (divisionsPriQ.isEmpty()) {
                     noMoreToAdd = true;
                  }
                  divisionsPriQ.addAll(pausedDivisions);
                  pausedDivisions.clear();
               }
            } else { // Otherwise place division on pausedDivision list.
               pbList.addAll(nonContiguous);
               pbList.addAll(nonSatisfactory);
               pausedDivisions.add(division);
               System.out.println("VorReg.dD - division paused: "
                     + division.getName() + " with voting Population: "
                     + division.getVotingPopulation());
            }
         }
      }
      System.out.println("VorReg.dD.  Unused Booths: " + booths.size());
      for (PollingBooth pb : booths) {
         System.out.println(pb.getName());
      }
   }

}
